Image information, be it color or black and white, is commonly generated in a bitmap format at a particular scale, orientation .THETA. and resolution K.times.L.times.b, corresponding to a desired printer output, where K is a number of spots per unit length in one dimension, L is a number of spots per unit length in the other dimension, and b is the depth of each pixel, in number of levels. This bitmap is present for every color separation of an output device, i.e., 4 bitmaps for a 4-color output device, 3 for a 3-color device, 2 for a 2-color device and 1 for a black and white output device. In a common example of a black and white output, image data comprising a bitmap to be printed is provided to a printer suitable for printing at 300 spots per inch (spi) in both dimensions, at a one bit depth, giving 2 levels. Many considerations drive this single selection of resolution, including the desirability of providing only a limited number of fonts (alphanumeric bitmaps) so as to use only a limited amount of storage space. Common software packages available on personal computers or for operation of input scanners for document creation are also usually provided with only a single resolution output. Images are commonly arranged at a fixed orientation .THETA..
Increasingly, the resolution available from printers varies over a wide range of choices. Printer resolutions are available over a range, for example, from less than 200 spi to more than 600 spi. Resolutions vary for a number of reasons, generally related to the quality of the output image. Simply printing a 300 spi bitmap at 400 spi or 600 spi is undesirable however, since the image will be reduced substantially in size on the output page or display (a practice commonly called scaling). It would be highly desirable to provide the capability of printing any image at any resolution, while selecting the output size and orientation.
It is a common practice to implement conversion of a bitmap of first resolution K.times.L.times.b to a bitmap of second resolution M.times.N.times.d through simple pixel level and raster level operations, such as pixel doubling. Pixel doubling is undesirable at the binary level (where printing is commonly done, with binary printers) because of a tendency to distort pixel relationships.
Conventional rotation of bitmaps is accomplished by moving groups of adjacent pixels along the fast scan direction by pixel distances in the slow scan direction, in accordance with their position with respect to the beginning of the scan line and thereby does not change the distribution of the image values, and will commonly produce moire or other artifacts.
A primary problem of the art is that the density in any given area of coverage is not maintained with pixel doubling or similar methods. Thus, image artifacts which give the image a different appearance are noted in the resolution-converted and/or rotated image.
These problems are less severe in the non-binary case, where scaling for 8 bit (256 levels) images is commonly done using gray level interpolation. These techniques can be applied to binary images by treating them as gray level images, resulting in a number of output levels far exceeding the number of allowed levels. Rotation of images may be accomplished using the three shear rotation method described in "A Fast Algorithm for General Raster Rotation", Graphics Interface '86, A. Paeth, p. 77 ff. (1986) or any other standard image rotation method by treating the input bitmap as a gray image having say 8 bits per pixel, and thereby creating an 8 bit rotated image which, in general, has a different distribution of values than the input, e.g. an image with only values of 0 and 1 will, in general, result in an image with a large number of pixels having values unequal to either 0 and 1.
Algorithms that convert gray images to binary or other number of level images attempting to preserve the local density exist in applications separate from image conversion. These and similar methods might be applied as one part of methods of image conversion. One method, which can be used to prepare an image at a given resolution and level depth of K.times.L.times.c for printing on a printer with resolution K.times.L.times.d, is error diffusion as described in "An Adaptive Algorithm for Spatial Greyscale, by Floyd and Steinberg, Proc. of the S.I.D. 17/2, 75-77 (1976). Another, more elaborate method would be the error diffusion techniques of U.S. patent application 07/396,272, entitled, "Edge Enhanced Error Diffusion Algorithm" by R. Eschback and the error diffusion techniques described in 07/600,542, entitled, "Method for Making Image Conversions With Error Diffusion" by R. Eschbach, both assigned to the same assignee as the present invention.
U.S. Pat. No. 4,651,287 to Tsao and U.S. Pat. No. 4,811,239 to Tsao disclose a technique which uses an error diffusion algorithm to produce high quality images wherein the gray scale values are compared to the discrete gray scale values of a reference printed array to produce a corresponding error array. U.S. Pat. No. 4,668,995 to Chen et al. discloses a quantization error diffusion algorithm for transforming a multi-bit image into a binary image by diffusing a propagation error among neighboring blocks of pixels. U.S. Pat. No. 4,654,721 to Goertzel et al. suggests printing of gray data on a binary printer, where the gray data is normally of a lower resolution and one takes one gray pixel and transfers it into one `dot`, i.e. a number of binary pixels in the output. Goertzel determines the form and location of those dots using error diffusion and edge enhancement. U.S. Pat. No. 4,783,838 to Matsunawa discloses a multi-step technique which first divides the binary image into blocks of pixels in order to generate a gray-tone representation of the image. Image processing and enhancement can be performed on these blocks and the processed blocks are then converted to the output bitmap using a conventional threshold matrix. U.S. Pat. No. 4,742,553 to Irwin teaches mapping of similarly sized input and output pixel groups, and the use of an error passing process to account for thresholding errors in a resolution conversion process.
In U.S. patent application Ser. No. 07/600,542, a form of error diffusion was proposed in which weighted portions of the error term occurring in the thresholding step of the error diffusion process are directed to adjacent pixels depending on whether the adjacent pixels are gray, or already black or white (legal values, in binary printing), or distributed corresponding to a fixed weighting scheme if all the adjacent pixels are already black or white to use the binary case as an example. While useful results are obtained in a number of image conversions using this method, an image defect is noted at the end of long single bit lines at certain conversion ratios. This artifact, sometimes known as a teardrop because of its appearance, is unsightly and undesirable. Additionally, in the application of documents, it is often undesirable to correct the density errors made in one object, e.g. character, by compensating another object or character that is separated by white space (legal values).